// 47.[DFS递归含重复swap] 全排列 II
// https://leetcode.cn/problems/permutations-ii/
// https://www.cnblogs.com/grandyang/p/4359825.html
//给定一个可包含重复数字的序列 nums, [-10,10]按任意顺序 返回所有不重复的全排列。
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
#include <bits/stdc++.h>
using namespace std;
#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif
class Solution {
  //  1,2,3,3,3,4,4,4
  //  考虑idx是否加入path
  void dfs(int idx, vector<int> path) {
    if (idx == nums_.size()) {
      res_.push_back(path);
      return;
    }
    for (size_t i = 0; i < nums_.size(); i++) {
      if (vtVisited_[i]) continue;
      if (i > 0 && nums_[i - 1] == nums_[i] && vtVisited_[i - 1]) {
        continue;
      }
      path.push_back(nums_[i]);
      vtVisited_[i] = 1;
      dfs(idx + 1, path);
      vtVisited_[i] = 0;
      path.pop_back();
    }
  }
  vector<int> nums_;
  vector<int> vtVisited_;
  vector<vector<int>> res_;

 public:
  vector<vector<int>> permuteUnique(vector<int> nums) {
    nums_ = nums;
    std::sort(nums_.begin(), nums_.end());
    vtVisited_.resize(nums.size(), 0);
    dfs(0, {});
    return res_;
  }
};
int main() {
  Solution sol;
  vector<vector<int>> out = sol.permuteUnique({1, 2, 3, 3});
  for (auto vt : out) {
    for (auto n : vt) PF("%d,", n);
    PF("\n");
  }
  return 0;
}